The provisioning of two parties with a shared secret key for symmetric-key cryptography presents a number of challenges including security of the provisioning and authentication of the recipient parties. This is true whether the keys are provisioned by physical distribution or by electronic means. Electronic provisioning is generally much preferable due to the very high cost and inconvenience of physical distribution.
A well known technique for electronic key provisioning is the Diffie-Hellman (DH) key exchange algorithm (see W. Diffie & M. E. Hellman, “Privacy and Authentication: An Introduction to Cryptography”, Proceedings of the I.E.E.E., vol. 67, No. 3, March 1979). For this algorithm, public system parameters p, q and g are defined; when parties A and B with respective secrets xA and xB wish to share a symmetric key, each sends the other the public parameter g raised to the power of its respective secret. Thus, A sends B gxA mod p, and B sends A gxB mod p. The receiving party then raises the received value to the power of its own secret so that each ends up with the value gxAxB mod p which can be used as a symmetric key. A key formed in this way is referred to herein as a Diffie-Hellman or DH key.
Of course, this mechanism for provisioning two parties with a shared key does not provide any guarantee to either party regarding the identity of the other party. Accordingly, authenticated key agreement protocols have been devised that effectively combine a key agreement protocol, such as the above-described DH key exchange protocol, and functionality such that at the end of the protocol, the two parties are convinced with whom they share the session key.
Authentication information can take the form either of keys (assumed to be of high cryptographic quality) or of passwords (a small secret value, such as a PIN code or an eight character alphanumeric string, that is presumed to be unsafe for direct use as a cryptographic key, but remains, nevertheless, a valuable and safe authentication factor when properly used).
Key-based authentication involves the knowledge of the two parties' long term key(s): either asymmetric (public/private) key pairs or a pre-shared symmetric secret key. The major drawback of basing authentication on a cryptographic key is the inability of a human user to remember a cryptographically secure key without assistance.
The present invention is concerned with the use of passwords to authenticate the participants in a cryptographic protocol such as a key agreement protocol.
Password-based authenticated key agreement is a well explored and widely used cryptographic primitive. It is typically suitable for a server-client environment, where a client represents a human user typically capable of remembering a password but not a full size key. Although a password is a weak secret and is vulnerable to dictionary attack, in a properly constructed password-based authenticated key agreement scheme, the communication between the client and server over a public channel is secure against the dictionary attack.
There are two main types of password-based authenticated key agreement scheme:                (1) The two parties use the same password in the scheme protocol; this kind of scheme is called a ‘balanced’ scheme. One example is SPEKE (Simple Password Exponential Key Exchange) which basically comprises a DH key exchange where the generator g is created from a hash of the password. See U.S. Pat. No. 6,226,383.        (2) One party (typically the client in a client-server arrangement) uses the password and the other party (for example, the server) uses a digest of the password; this kind of scheme is called an ‘augmented’ scheme. One example is SRP-3 (Secure Remote Password). See IETF RFC 2945.        
Where an existing password-based authenticated key agreement protocol is employed in the client server context, the server needs to store securely in its database the unique passwords (or password digests) of a possibly large number of clients, in order to be able to authenticate each client. Then, each time the protocol is run, the server must retrieve the password or the digest of the password and use it in the protocol. If an adversary is able to access the server's database or to spy on the server's processing, the adversary will be able to get the password or to search the password. Reducing the vulnerability of the client's password at the server is clearly desirable and one way of doing this is for the server to employ a long-term strong secret key to encrypt each password (or its digest). The server then decrypts each stored encrypted client password (or digest) before using it in the password-based authenticated key agreement protocol; after use, the decrypted password (or digest) is erased. Obviously, this approach is inefficient and still leaves the password/digest vulnerable during the running of the protocol. Furthermore, in some contexts, the memory available to the server for storing password-related data may be constrained, effectively limiting the number of users that the server can service.